// 请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<set>
#include<queue>
#include<stack>
using namespace std;

// 看了题解，单调栈
// 执行用时：
// 148 ms
// , 在所有 C++ 提交中击败了
// 52.16%
// 的用户
// 内存消耗：
// 86.9 MB
// , 在所有 C++ 提交中击败了
// 11.91%
// 的用户

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> sta;
        vector<int> res(temperatures.size(),0);
        sta.push(0);
        for(int i=1;i<temperatures.size();i++){
            if(temperatures[sta.top()]>temperatures[i]){
                sta.push(i);
            }
            else if(temperatures[sta.top()]==temperatures[i]){
                sta.push(i);
            }
            else{
                while(!sta.empty() && temperatures[sta.top()]<temperatures[i]){
                    res[sta.top()] = i-sta.top();
                    sta.pop();
                }
                sta.push(i);
            }
        }
        return res;
    }
};